#!/usr/bin/env python
# -*- coding:utf-8 -*-
'''
Given an integer n, return 1 - n in lexicographical order.
For example, given 13, return: [1,10,11,12,13,2,3,4,5,6,7,8,9].
Please optimize your algorithm to use less time and space. The input size may be as large as 5,000,000. 
'''
import datetime

# notes: split large functions to small functions, one small function best not exceed 20 lines.
class Solution(object):
    def lexicalOrder(self,n):
        """
        :type n: int
        :rtype: List[int]
        """
        list_a=[]
        cur = 1
        list_a.append(cur)
        for i in range(1, n):
            cur=self.next_number(cur, n)
            list_a.append(cur)
        return list_a

    def next_number(self, cur, max_limit):
        if cur * 10 <= max_limit:
            return cur * 10
        else:
            while cur % 10 == 9:
                cur = cur // 10
            if cur + 1 <= max_limit:
                return cur + 1
            else:
                return cur // 10 + 1 

class SolutionFromXudi(object):
    def next_number(self, n, limit):
        if n * 10 > limit:
            while n % 10 == 9:
                n /= 10
            if n + 1 <= limit:
                return n + 1
            return n / 10 + 1
        else:
            return n * 10
    
    def lexicalOrder(self, n):
        """
        :type n: int
        :rtype: List[int]
        """
        ret, cur = [], 1
        for _ in range(n):
            ret.append(cur)
            cur = self.next_number(cur, n)
        return ret

start_time=datetime.datetime.now()

solution=Solution()
print(solution.lexicalOrder(135))
print(solution.lexicalOrder(9))
print(solution.lexicalOrder(59))
solution.lexicalOrder(59035923)


end_time=datetime.datetime.now()
print(end_time - start_time)

